/*
 * @lc app=leetcode id=486 lang=cpp
 *
 * [486] Predict the Winner
 */

// @lc code=start
class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        int dp[21][21] = {0};
        for (int i = 0; i < n; ++i) {
            dp[i][i] = nums[i];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < n - i; ++j) {
                dp[j][j+i] = max(nums[j]- dp[j+1][j+i], nums[j+i] - dp[j][j+i-1]);
            }
        }
        return dp[0][n-1] >= 0;
    }
};
// @lc code=end

